package lc.二叉树;

import utils.TreeNode;

import java.util.Deque;
import java.util.LinkedList;


/**
 * @description:
 * @author: qian
 * @createDate: 2021/10/10
 */
public class Math101对称二叉树 {

    public boolean isSymmetric(TreeNode root) {

        Deque<TreeNode> deQueue = new LinkedList<>();
        deQueue.offerFirst(root.left);
        deQueue.offerLast(root.right);
        while (!deQueue.isEmpty()) {

            TreeNode pollLast = deQueue.pollLast();
            TreeNode pollFirst = deQueue.pollFirst();
            if (pollFirst == null && pollLast == null) {
                continue;
            }
            if (pollFirst == null || pollLast == null || pollLast.val != pollFirst.val) {
                return false;
            }
            deQueue.offerFirst(pollLast.left);
            deQueue.offerFirst(pollLast.right);
            deQueue.offerLast(pollFirst.right);
            deQueue.offerLast(pollFirst.left);
        }
        return true;

    }

    public boolean isSymmetric1(TreeNode root) {
        if (root == null){
            return true;

        }
        return is(root.left,root.right);
    }
    private boolean is(TreeNode l,TreeNode r){
        if (l == null && r == null){
            return true;
        }
        if (l == null || r == null || l.val !=r.val){
            return false;
        }
        return is(l.left,r.right) && is(l.right,r.left);
    }
}
